COMP90038
Algorithms and Complexity
Lecture 6: Recursion
(with thanks to Harald Søndergaard)
Toby Murray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Recursion
We’ve already seen some examples
•
A very natural approach when the data structure is
•
recursive (e.g. lists, trees)
But also examples of naturally recursive array
•
processing algorithms
•
Next week we’ll express depth first graph traversal recursively (the natural way); later we’ll meet other examples of recursion too
Example: Factorial
n!: we can use recursion (left) or iteration (right)
•
F(5) =F(4)⋅5
= (F(3) ⋅ 4) ⋅ 5
= ((F(2) ⋅ 3) ⋅ 4) ⋅ 5
= (((F(1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5
= ((((F(0) ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = ((((1 ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5
= 120
n: 420315
result: 61521200
Iterative version normally preferred since it is constant space
3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
4
Complexity is exponential in n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Fibonacci Numbers
Follows the mathematical definition of Fibonacci numbers very closely.
Easy to understand
But performs lots of redundant computation
To generate the nth number of sequence: 1 1 2 3 5
•
8 13 21 34 55 …
Basic operation: addition
Fibonacci Again
Of course we only need to remember the latest two
•
items. Recursive version: left; iterative version: right
Initial call: Fib(n, 1, 0) Time complexity of both
solutions is linear in n
(There is a cleverer, still recursive, way which is O(log n).)
5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Tracing Recursive Fibonacci
6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Initial call: Fib(5, 1, 0)
Fib(5,1,0)
= Fib(4,1,1)
= Fib(3,2,1)
= Fib(2,3,2)
= Fib(1,5,3)
= Fib(0,8,5) =8
Fibonacci Sequence:
1 12 3 5 8 …
Tower of Hanoi
Init Aux Fin
Move n disks from Init to Fin. A larger disk can never be placed on top of a smaller one.
7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Tower of Hanoi:
Recursive Solution
Init Aux Fin Move n-1 disks from Init to Aux.
8 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Tower of Hanoi:
Recursive Solution
9
Init Aux Fin Move n-1 disks from Init to Aux.
Then move the nth disk to Fin.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Tower of Hanoi:
Recursive Solution
Init Aux Fin
Move n-1 disks from Init to Aux. Then move the nth disk to Fin. Then move the n-1 disks from Aux to Fin.
10 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Tower of Hanoi:
Recursive Solution
Init Aux Fin
Move n-1 disks from Init to Aux. Then move the nth disk to Fin. Then move the n-1 disks from Aux to Fin.
11 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Tower Of Hanoi: Recursive Algorithm
Init Aux Fin
12 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Tracing Tower of Hanoi Recursive Algorithm
http://vornlocher.de/tower.html
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
A Challenge:
Coin Change Problem
There are 6 different kinds of Australian coin
In cents, their values are: 5, 10, 20, 50, 100, 200
In how many different ways can I produce a handful of coins adding up to $4?
This is not an easy problem!
• • •
•
Key to solving it is to find a way to break it down
•
into simpler sub-problems
Coin Change Problem:
Decomposition
$4 made from
Does the bag contain a $2 coin? Yes No
+
made from
$2 $4
made from
15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Coin Change Problem: Decomposition
The number of ways of making $4 is therefore:
16
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
1 x the number of ways of making $2
+
the number of ways of making $4 without using a $2 coin
Coin Change Problem:
Partial Algorithm
function WAYS(amount, denominations) // … base cases ….
d ← selectLargest(denominations)
return WAYS(amount − d, denominations) +
WAYS(amount, denominations \ {d})
For example:
Ways(400, {5,10,20,50,100,200}) = Ways(200, {5,10,20,50,100,200}) +
Ways(400, {5,10,20,50,100})
17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
18
Coin Change Problem: Base Cases
Each time we recurse, we decrease either:
amount (by subtracting some quantity from it), or
•
•
demonisations (by removing an item from the set) •
•
Consider each of these separately.
amount base cases:
amount = 0: there is one way (using no coins)
amount < 0: there are no ways to make this denominations = ∅ (and amount > 0):
there are no ways to make this amount Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
•
•
• •
Coin Change Problem: Full Recursive Algorithm
function WAYS(amount, denominations)
if amount = 0 then
return 1
if amount < 0 then
return 0
if denominations = ∅ then
return 0
d ← selectLargest(denominations)
return WAYS(amount − d, denominations) + WAYS(amount, denominations \ {d})
Initial call: WAYS(amount, {5, 10, 20, 50, 100, 200}).
19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
20
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Recursive Solution and its
Complexity
Although our recursive algorithm is short and elegant, it is not the most efficient way of solving the problem.
•
•
More efficient solutions can be developed using memoing or dynamic programming—more about that later (around Week 10).
Its running time grows exponentially as you grow
•
the input amount.
21
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Next Time...
Graphs, trees, graph traversal and allied
•
algorithms.